
/**
 * Given a positive integer num, write a function which returns True if num is a
 * perfect square else False.
 * <p>
 * Follow up: Do not use any built-in library function such as sqrt.
 * <p>
 * <p>
 * Example 1:
 * Input: num = 16
 * Output: true
 * <p>
 * Example 2:
 * Input: num = 14
 * Output: false
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= num <= 2^31 - 1
 * <p>
 * <p>
 * Related Topics 数学 二分查找 👍 450 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00367ValidPerfectSquare {
    public static void main(String[] args) {
        Solution solution = new ID00367ValidPerfectSquare().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isPerfectSquare(int num) {
            int left = 1;
            int right = num;

            int maxValue = (int) Math.sqrt(Integer.MAX_VALUE);

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (mid * mid == num) {
                    return true;
                } else if (mid > maxValue || mid * mid > num) {
                    right = mid - 1;
                } else if (mid * mid < num) {
                    left = mid + 1;
                }


            }

            return false;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}